M2.855 · Modelos avanzados de minería de datos · PEC2

2021-1 · Máster universitario en Ciencia de datos (Data science)

Estudios de Informática, Multimedia y Telecomunicación

 

PEC 2: Métodos no supervisados

A lo largo de esta práctica veremos como aplicar distintas técnicas no supervisadas así como algunas de sus aplicaciones reales:

Nombre y apellidos:

Para ello vamos a necesitar las siguientes librerías:

1. Métodos de clustering (4 puntos)

Este ejercicio trata de explorar distintas técnicas de agrupamiento ajustándolas a distintos conjuntos de datos.

El objetivo es doble: entender la influencia de los parámetros en su comportamiento, y conocer sus limitaciones en la búsqueda de estructuras de datos.

Generación de los conjuntos de datos

Cada dataset tiene 2 variables: una variable X que contiene 2 features (columnas) y tantas filas como muestras. Y una variable y que alberga las etiquetas que identifican cada cluster.

A lo largo del ejercicio no se usará la variable y (sólo con el objetivo de visualizar). El objetivo es a través de los distintos modelos de clustering conseguir encontrar las estructuras descritas por las variables y.

1 a. K-means

En este apartado se pide probar el algoritmo k-means sobre los tres datasets presentados anteriormente ajustando con los parámetros adecuados y analizar sus resultados.

Para estimar el número de clusters a detectar por k-means. Una técnica para estimar $k$ es, como se explica en la teoría:

Los criterios anteriores (minimización de distancias intra grupo o maximización de distancias inter grupo) pueden usarse para establecer un valor adecuado para el parámetro k. Valores k para los que ya no se consiguen mejoras significativas en la homogeneidad interna de los segmentos o la heterogeneidad entre segmentos distintos, deberían descartarse.

Lo que popularmente se conocer como regla del codo.

Primero es necesario calcular la suma de los errores cuadráticos (SSE) que consiste en la suma de todos los errores (distancia de cada punto a su centroide asignado) al cuadrado.

$$SSE = \sum_{i=1}^{K} \sum_{x \in C_i} euclidean(x, c_i)^2$$

Donde $K$ es el número de clusters a buscar por k-means, $x \in C_i$ son los puntos que pertenecen a i-ésimo cluster, $c_i$ es el centroide del cluster $C_i$ (al que pertenece el punto $x$), y $euclidean$ es la distancia euclídea.

Este procedimiento realizado para cada posible valor $k$, resulta en una función monótona decreciente, donde el eje $x$ representa los distintos valores de $k$, y el eje $y$ el $SSE$. Intuitivamente se podrá observar un significativo descenso del error, que indicará el valor idóneo de $k$.

Se pide realizar la representación gráfica de la regla del codo junto a su interpretación, utilizando la librería matplotlib y la implementación en scikit-learn de k-means.

Implementación: cálculo y visualización de la regla del codo en el dataset Blobs.
Solución:
Análisis: ¿Qué se interpreta en la gráfica? ¿Cómo podría mejorarse la elección de $k$?.
Solución:

Tal y como se esperaba, en la gráfica anterior puede observarse como a medida que aumenta el número de clusters se va reduciendo el error. A partir de $k=4$, el error se reduce significativamente y no se aprecia una notable reducción del error al aumentar el valor de $k$. Por lo que una decisión razonable es pensar que el número de clusters originales es de 4.

Se puede afinar más con una métrica que no sólo utilice la distancia intra-grupo sino también la inter-grupo. Tal y como aparece en la teoría.
Implementación: cálculo y visualización de los grupos en el dataset Blobs.
Solución:
Análisis: ¿Qué ha sucedido? Explica los motivos por los que crees que se ha producido ese resultado.
Solución:

Usando k-means con distancia euclídea asumimos que los clusters son n-esferas. En la práctica podemos verlo como una teselación de Voronoi, que es lo que se observa en los resultados anteriores. Separando los distintos blobs de forma aceptable.
Implementación: cálculo y visualización de la regla del codo en el dataset Moons.
Solución:
Análisis: ¿Qué se interpreta en la gráfica? ¿Cómo podría mejorarse la elección de $k$?.
Solución:

En este caso no es tan fácil distinguir un *k* adeucado. Y no coincide con los dos esperados.
Implementación: cálculo y visualización de los grupos en el dataset Moons.
Solución:
Análisis: ¿Qué ha sucedido? Explica los motivos por los que crees que se ha producido ese resultado.
Solución:

Usando k-means con distancia euclídea asumimos que los clusters son n-esferas. En la práctica podemos verlo como una teselación de Voronoi, que es lo que se observa en los resultados anteriores.

Es normal que no se produzcan los resultados esperados porque los clusters tienen distintas formas y no se ciñen a celdas de Voronoi.
Implementación: cálculo y visualización de la regla del codo en el dataset Circles.
Solución:
Análisis: ¿Qué se interpreta en la gráfica? ¿Cómo podría mejorarse la elección de $k$?.
Solución:

En este caso no es tan fácil distinguir un *k* adeucado. Y no coincide con los dos esperados.
Implementación: cálculo y visualización de los grupos en el dataset Circles.
Solución:
Análisis: ¿Qué ha sucedido? Explica los motivos por los que crees que se ha producido ese resultado.
Solución:

Usando k-means con distancia euclídea asumimos que los clusters son n-esferas. En la práctica podemos verlo como una teselación de Voronoi, que es lo que se observa en los resultados anteriores.

Es normal que no se produzcan los resultados esperados porque los clusters tienen distintas formas y no se ciñen a celdas de Voronoi.

1 b. Algoritmos basados en densidad: DBScan

En este apartado se pide aplicar clustering por densidad como DBSCAN a los datasets anteriores para detectar los grupos subyacentes.

Implementación: prueba la implementación de DBSCAN en scikit-learn jugando con los parámetros eps y min_samples para encontrar los grupos (y outliers) del dataset Blobs.
Solución:
Análisis: ¿Qué ha sucedido? Explica los motivos por los que crees que se ha producido ese resultado.
Solución:

Usando DBSCAN con un eps de 2.2 se consigue encontrar los cuatro clusters porque tienen mucha densidad en su centro y están suficientemente separados. Eso hace que al guiarse por la densidad de puntos se puedan distinguir las estructuras.
Implementación: prueba la implementación de DBScan jugando con los parámetros eps y min_samples para encontrar los grupos (y outliers) del dataset Moons.
Solución:
Análisis: ¿Qué ha sucedido? Explica los motivos por los que crees que se ha producido ese resultado.
Solución:

Usando DBSCAN con un eps de 0.15 se consigue encontrar ambos clusters porque ambas lunes tienen una densidad constante a lo largo de cada uno de ellas y están suficientemente separadas. Eso hace que al guiarse por la densidad de puntos se puedan distinguir ambas estructuras.
Implementación: prueba la implementación de DBScan jugando con los parámetros eps y min_samples para encontrar los grupos (y outliers) del dataset Circles.
Solución:
Análisis: ¿Qué ha sucedido? Explica los motivos por los que crees que se ha producido ese resultado.
Solución:

Usando DBSCAN con un eps de 0.12 se consigue encontrar ambos clusters porque ambos anillos tienen una densidad constante a lo largo de cada uno de ellos y están suficientemente separados. Eso hace que al guiarse por la densidad de puntos se puedan distinguir ambas estructuras.

1 c. Algoritmos jerárquicos

En este apartado se pide visualizar mediante un dendrograma la construcción progresiva de los grupos mediante un algoritmo jerárquico aglomerativo (estrategia bottom-up). Con ello se pretende encontrar un método gráfico para entender el comportamiento del algoritmo y encontrar los clusters deseados en cada dataset.

Implementación: prueba la implementación de clustering jerárquico de scipy probando distintos criterios de enlace o linkage permitiendo identificar los clusters subyacentes (mostrando su resultado) y su dendrograma para el dataset Blobs.
Puedes importar las librerías necesarias para ello.
Solución:
Análisis: Interpreta el dendrograma y comenta qué criterio de enlace se ha comportado mejor. ¿Por qué?
Solución:

Los enlaces complete y ward son los que, para este dataset, permite distinguir mejor los clusters esperados.

Ya que hay dos nubes muy cerca por lo que el enlace simple las hace dificilmente distinguibles.
Implementación: prueba la implementación de clustering jerárquico de scipy probando distintos criterios de enlace o linkage permitiendo identificar los clusters subyacentes (mostrando su resultado) y su dendrograma para el dataset Moons.
Puedes importar las librerías necesarias para ello.
Solución:
Análisis: Interpreta el dendrograma y comenta qué criterio de enlace se ha comportado mejor. ¿Por qué?
Solución:

El enlace simple es el que, para este dataset, permite distinguir mejor los clusters esperados.

El enlace simple, definido como la mínima distancia entre elementos de cada cluster:

$$d(A, B)\min\{\,d(x,y):x\in A,\,y\in B\,\}$$
Donde $x$ e $y$ son elementos de distintos clusters ($A$ y $B$). La intuición detrás de este criterio de enlace es ir juntando los clusters a través de sus puntos más próximos. De esta forma, se van dibujando las formas de los clusters, permitiendo encontrar formas complejas bien separadas entre ellas.
Implementación: prueba la implementación de clustering jerárquico de scipy probando distintos criterios de enlace o linkage permitiendo identificar los clusters subyacentes (mostrando su resultado) y su dendrograma para el dataset Circles.
Puedes importar las librerías necesarias para ello.
Solución:
Análisis: Interpreta el dendrograma y comenta qué criterio de enlace se ha comportado mejor. ¿Por qué?
Solución:

El enlace simple es el que, para este dataset, permite distinguir mejor los clusters esperados.

El enlace simple, definido como la mínima distancia entre elementos de cada cluster:

$$d(A, B)\min\{\,d(x,y):x\in A,\,y\in B\,\}$$
Donde $x$ e $y$ son elementos de distintos clusters ($A$ y $B$). La intuición detrás de este criterio de enlace es ir juntando los clusters a través de sus puntos más próximos. De esta forma, se van dibujando las formas de los clusters, permitiendo encontrar formas complejas bien separadas entre ellas.

2. Aplicación: generación de imágenes con reducción de dimensionalidad (3 puntos)

Es posible aplicar una amplia variedad de algoritmos para la reducción de dimensionalidad. Para ello se empleará el dataset MNIST compuesto de miles de dígitos manuscritos del 0 al 9. Donde cada imagen se compone de 784 píxeles (imágenes de 28 x 28), por lo que se parte de un número alto de dimensiones.

Por lo que cada muestra (las 70k filas del dataset) se componen de 784 dimensiones:

Si cada algoritmo obtiene resultados distintos a la hora de reducir la dimensionalidad, ¿qué representación es más fiel a la distribución original?

Antes de reducir las 784 dimensiones originales de cada muestra a 2 para poder visualizarlas en 2 dimensiones, es muy útil conocer, o al menos intuir, la estructura en alta dimensionalidad de los datos.

Para ello se puede hacer uso del dendrograma como heurística para conocer la disposición original de los datos y comprobar si la proyección es similar a lo mostrado por el dendrograma.

Implementación: aprender una proyección a 2 dimensiones de las muestras de X con PCA y proyectar el conjunto X a dos dimensiones. Después visualizarlo en un scatter plot. Utiliza las etiquetas de y (el número manuscrito al que se corresponde cada muestra), en el parámetro label (en la llamada a scatter) y la función legend en la visualización para saber la clase correspondiente a cada punto e interpretar el resultado de la reducción de dimensionalidad y poder interpretar el resultado de la proyección.
Solución:
Análisis: ¿Qué puedes interpretar de la proyección? ¿Las clases han quedado visiblemente separadas? ¿Por qué?
Solución: Hay varias clases que se distinguen fácilmente de las otras, pero muchas de ellas están solapadas entre sí. No están claramente separadas. PCA aplica una proyección lineal y en este caso limita la representación final. También se trata de aprendizaje no supervisado, por tanto su objetivo no es la separabilidad.

En la gráfica anterior cada punto representa una muestra en 2 dimensiones. Con PCA es posible invertir la transformación para que, a partir de cada punto 2d, se obtenga de nuevo (aproximadamente) la imagen original (784 dimensiones).

Por lo que es posible "generar" nuevas imágenes eligiendo puntos aleatoriamente del plano 2d, y pedirle al modelo PCA aprendido que invierta la transformación para obtener las "teóricas" imágenes que habrían sido proyectadas a esos puntos del espacio proyectado.

Implementación: calcular el máximo y mínimo de cada una de las dos dimensiones y, para cada una de ellas, generar una secuencia de 10 valores con igual separación.
Solución:

Con las dos secuencias de 10 (una por cada dimensión del plano de proyección) valores es posible combinar los puntos de ambas secuencias para generar 100 combinaciones (puntos 2d) que teselan el plano sobre el que PCA ha proyectado las muestras.

Implementación: invertir la transformación para cada uno de los 100 puntos y visualizar su imagen asociada en una matriz de 10 x 10 imágenes (tratando de preservar su posición en el espacio proyectado).
Solución:
Análisis: ¿Qué puedes interpretar de las imágenes reconstruídas / interpoladas? ¿Genera números o transiciones entre números visualmente creíbles? ¿Por qué?
Solución: parecen distinguirse números, entre ellos el 0, 1 y 9. Pero no tan claros los demás. No parece que sean números que produzca una persona. La limitación de la proyección lineal puede ser la causa de ello.
Análisis: ¿Podría haberse conseguido lo mismo con t-SNE? ¿Por qué?
Solución: no, ya que t-SNE no puede invertir la transformación ya que lo trata como un problema de optimización en el que desplaza los puntos en sí en lugar de aprender un manifold sobre el que proyectar.
Implementación: aprender una proyección a 2 dimensiones de las muestras de X con UMAP (con los parámetros por defecto) usando la librería umap-learn y proyectar el conjunto X a dos dimensiones. Después visualizarlo en un scatter plot. Utiliza las etiquetas de y (el número manuscrito al que se corresponde cada muestra), en el parámetro label (en la llamada a scatter) y la función legend en la visualización para saber la clase correspondiente a cada punto e interpretar el resultado de la reducción de dimensionalidad y poder interpretar el resultado de la proyección.
Solución:
Análisis: ¿Qué puedes interpretar de la proyección? ¿Las clases han quedado visiblemente separadas? ¿Por qué?
Solución: los grupos de números están bastante separados. Los grupos que permanecen cerca son números que pueden fácilmente confundirse entre sí en función de la grafía, como el 4, 5, y 9. La no linelidad permite aprender un manifold con una topología más expresiva.
Implementación: al igual que anteriormente con PCA, calcula el máximo y mínimo para cada una de las dos dimensiones e invierte la transformación con el modelo aprendido por UMAP para cada uno de los 100 puntos y visualizar su imagen asociada en una matriz de 10 x 10 imágenes (tratando de preservar su posición en el espacio proyectado). Consejo: la inversión de la transformación en UMAP es más costosa computacionalmente que con PCA, por lo que recomiendo que sólo la invoques una vez con las 100 muestras en lugar de hacer 100 llamadas (una por cada muestra). Esto reduce drácticamente el tiempo de ejecución.
Solución:
Análisis: ¿Qué puedes interpretar de las imágenes reconstruídas / interpoladas? ¿Genera números o transiciones entre números visualmente creíbles? ¿Por qué?
Solución: es este caso sí que se pueden distinguir más números manuscritos con apariencia real y las transiciones entre éstos a medida que se elige un punto del espacio situado entre dos grupos de números.

3. Aplicación: identificación de puntos de interés turísticos (3 puntos)

En este ejercicio se busca automatizar la localización de lugares turísticos a través de los metadatos de las fotografías de flickr.

Para ello se provee junto a la PEC el dataset: barcelona.csv. Ya que se pide encontrar los puntos de mayor interés turístico de esta ciudad.

Opcional: si quieres hacerlo para otra región

Pero si quieres hacerlo para otra parte del mundo, puedes descargarte el dataset completo aquí y descomprime para extraer el CSV.

Para seleccionar las coordenadas de la zona de interés puedes usar la opción Export manual de OpenStreetMaps.

Por último, para filtrar los datos que se corresponden a la zona deseada puedes usar el programa AWK mediante la siguiente línea:

awk -F"," 'NR == 1 {print $5","$6} (NR > 1 && $5 > 41.3560 && $5 < 41.4267 && $6 > 2.1300 && $6 < 2.2319) {print $5","$6}' photo_metadata.csv

$5 hace referencia a la latitud, y $6 a la longitud. Sustituye los valores mínimo y máximo para obtener los datos de localización referentes a tu área de interés.

Implementación: siempre que tratamos un problema real, es necesario entender los datos a tratar. Visualiza las localizaciones de las fotografías mediante un scatter plot. Prueba distintos parámetros de tamaño (size) s, y opacidad alpha hasta conseguir un resultado fácil de interpretar.
Solución: sí, la distribución de los puntos adopta la forma de la península. t-SNE trata de mantener las distancias ha conseguido situarlas en el mapa. La forma aparece girada porque no tiene forma de saber solo con las distancias su orientación real.
Análisis: tras haber probado los algoritmos de agrupamiento en el ejercicio 1. ¿Qué algoritmo crees que sería más adecuado tras visualizar los datos? ¿Por qué?
Solución: mejor un algoritmo basado en densidad dado que hay clusters con formas diversas, por lo que queda descartado k-means. Por otro lado, hay mucho ruido de fondo (puntos que no pertenecen a un punto turístico), por lo que DBScan es muy últil en este caso frente a la aproximación jerárquica.
Implementación: para prototipar el modelado primero se recomienda elegir un subconjunto de los datos que sea representativo. Selecciona una muestra del DataFrame original y visualiza como en el punto anterior para comprobar su similitud.
Solución:
Implementación: ajusta el algoritmo de clustering elegido para encontrar los distintos grupos sobre el conjunto reducido, y visualiza el resultado coloreando cada punto en base al grupo al que pertenece. Como pista, alrededor de 20 clusters es un número razonable, y es posible darles un color distinto a cada uno con el colormap: tab20.
Solución:
Implementación: si has usado un método de clustering que permite la detección de outliers. Representa sólo los puntos que no ha considerado outliers, es decir, los que pertenecen a algún cluster.
Solución:
Análisis: interpreta cual es el lugar que representa cada cluster (si encuentras una asociación lógica).
Solución: Es fácil encontrar varios sitios típicos como: el centro, la parte baja de la rambla, colón, la playa, la ciudadela, paseo de gracia, la pedrera, parc Guel, la sagrada família, montjuic, final de la diagonal...
OPCIONAL Implementación: representa los puntos sin ruido sobre un mapa utilizando la librería Smopy. Para facilitar la interpretación, puedes representar cada cluster como el punto medio de todos los puntos que lo conforman.
Solución: